//
// Created by ZYZ on 2020/6/9.
// description: 双向链表也是有头结点的

#include <stdio.h>
#include <stdlib.h>
#include "double_direction_linked_list.h"
#include "../../include/type_list.h"

//初始化双链循环线性表          （默认只有一个空头结点）
void initDulLst(DuLinkList &l) {
    l = (DuLinkList) malloc(sizeof(DuLNode));
    l->next = l->prior = l;
}

//获取双链循环线性表中的元素     （双向链表也是有空结点的，这个空结点就是头结点）
DuLNode *GetElemP_Dul(DuLinkList linkList, int i) {
    DuLinkList p_temp = linkList;
    if (i < 1)   //非法i值
        return NULL;
    if (p_temp->next == linkList)           //空双向循环链表
        return linkList;
    p_temp = linkList->next;
    int j = 1;                              //初始化, p指向第一个结点, j为计数器
    while (p_temp != linkList && j < i) {   //顺指针向后查找, 直到p指向第i个元素或p指向头结点
        p_temp = p_temp->next;
        ++j;
    }
    return p_temp;
}

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
    //在带头结点的双链循环线性表 L 中第 i 个位置之前插入元素 e
    //i 的合法值为 1 <= i <= 表长 + 1

    DuLinkList p;
    if (!(p = GetElemP_Dul(L, i)))          //在 L 中确定插入位置
        return ERROR;                       //p = NULL，即插入位置不合法（i 不合法）

    DuLinkList s;
    if (!(s = (DuLinkList) malloc(sizeof(DuLNode)))) return ERROR; //申请一块 sizeof(DuLNode) 大小的内存，如果申请失败返回 ERROR

    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;

    return OK;
}//ListInsert_DuL


Status ListDelete_Dul(DuLinkList &L, int i, ElemType &e) {

    //删除带头结点的双链循环线性表 L 的第 i 个元素，i 的合法值为 1 <= i <= 表长
    DuLinkList p;
    if (!(p = GetElemP_Dul(L, i)))          //在 L 中确定第 i 个元素的位置指针 p
        return ERROR;                       //p = NULL，即第 i 个元素不存在

    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);

    return OK;
}//Listdelete-DuL


//遍历线性表
Status ListTraverse_DuL(DuLinkList L) {
    printf("--- traverse list: --- \n");
    struct DuLNode *p = L->next; //略过头结点
    while (p != L) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
